// https://leetcode.cn/problems/path-sum-ii/
// Created by ade on 2022/7/20.
// 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//
// 叶子节点 是指没有子节点的节点。

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector <vector<int>> res;

    vector <vector<int>> pathSum(TreeNode *root, int targetSum) {
//        dfs(root, 0, {}, targetSum);
        back(root, 0, targetSum);
        return res;
    }

    // dfs的效率比较低
    void dfs(TreeNode *node,  vector<int> tmp, int targetSum) {
        if (node) {
            targetSum -= node->val;
            tmp.emplace_back(node->val);
            if (!node->left && !node->right && targetSum == 0) {
                res.push_back(tmp);
                return;
            }
            dfs(node->left,  tmp, targetSum);
            dfs(node->right, tmp, targetSum);
        }
    }

    vector<int> tmp;

    // 回溯的效率更高一点
    void back(TreeNode *node, int sum, int &targetSum) {
        if (node) {
            sum += node->val;
            tmp.push_back(node->val);
            if (!node->left && !node->right && sum == targetSum) {
                res.push_back(tmp);
//                return; 回溯不能有return
            }
            back(node->left, sum, targetSum);
            back(node->right, sum, targetSum);
            tmp.pop_back();
        }
    }
};

int main() {
    Solution so;
    TreeNode *head = so.init();
    auto res = so.pathSum(head);
    for (auto i : res) {
        for (auto j:i) {
            cout << j << ",";
        }
        cout << endl;
    }
    return 0;
}